package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Liaorun
 */
public class MinOpToMakeElementsEqual {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(minOperation(a,new int[] {1}));
    }


    public static List<Long> minOperation(int[] nums, int[] queries) {
        int n = nums.length;
        Arrays.sort(nums);

        // 生成前缀和数组
        long[] sum = new long[n + 1];

        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }

        ArrayList<Long> ans = new ArrayList<>();

        int less, more;
        long curAns;

        for (int v : queries) {
            less = bs(nums, v);
            // 左侧需要的操作次数
            curAns = (long) (less + 1) * v - sum(sum, 0, less);
            more = bs(nums, v + 1);
            // += 右侧需要的操作次数
            curAns += sum(sum, more + 1, n - 1) - (long) (n - more - 1) * v;

            ans.add(curAns);
        }

        return ans;
    }

    /**
     * @param sum : the array of sum
     * @param l   左边界
     * @param r   : 右边界
     * @return 左边界到右边界中的元素和
     */
    private static long sum(long[] sum, int l, int r) {
        return l > r ? 0 : sum[r + 1] - sum[l];
    }

    private static int bs(int[] nums, int v) {
        int l = 0;
        int r = nums.length - 1;
        int m, ans = -1;

        // 左指针在右指针之前或者重合
        while (l <= r) {
            // 计算中点
            m = (l + r) / 2;
            if (nums[m] < v) {
                // 中点的值小于要查找的值 => 左指针移动到中点的下一个值
                l = m + 1;
                // 当前中点下标就是需要的结果
                ans = m;
            } else {
                // 中点的值大于or等于要查找的值 => 右指针移动到中点的前一个值
                r = m - 1;
            }
        }
        return ans;
    }
}
